package main

import "fmt"

// 一个单向链表 从尾到头打印节点元素

// 解法一 遍历链表将链表元素依次入栈，然后打印栈中元素

func ListPrint(root *ListNode) {
	if root == nil {
		return
	}
	stack := NewLinkedListStack()
	for root != nil {
		stack.Push(root.Val)
		root = root.Next
	}
	for !stack.IsEmpty() {
		n := stack.Pop()
		fmt.Println(n.(int))
	}
}

// 解法二 递归，打印一个节点元素的时候，先递归输出它后面的节点
// 链表太长容易栈溢出

func ListPrint2(root *ListNode) {
	if root == nil {
		return
	}
	if root.Next != nil {
		ListPrint2(root.Next)
	}
	fmt.Println(root.Val)
}

type node struct {
	next  *node
	value interface{}
}

type LinkedListStack struct {
	// 栈顶指针
	topNode *node
}

func NewLinkedListStack() *LinkedListStack {
	return &LinkedListStack{nil}
}

func (this *LinkedListStack) IsEmpty() bool {
	return this.topNode == nil
}

func (this *LinkedListStack) Push(v interface{}) {
	this.topNode = &node{next: this.topNode, value: v}
}

func (this *LinkedListStack) Pop() interface{} {
	if this.IsEmpty() {
		return nil
	}

	v := this.topNode.value
	this.topNode = this.topNode.next
	return v
}

func (this *LinkedListStack) Top() interface{} {
	if this.IsEmpty() {
		return nil
	}

	return this.topNode.value
}

func (this *LinkedListStack) Flush() {
	this.topNode = nil
}

func (this *LinkedListStack) Print() {
	if this.IsEmpty() {
		fmt.Println("empty stack")
	} else {
		cur := this.topNode
		for cur != nil {
			fmt.Println(cur.value)
			cur = cur.next
		}
	}
}
